public class num02_02 {
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode snow = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast != null){
            fast = fast.next;
            snow = snow.next;
        }
        return snow.val;
    }

    public static class offer68 {
        private TreeNode lca;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            find(root,p,q);
            return lca;
        }

        private boolean find(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null){
                return false;
            }
            int left = find(root.left,p,q) ? 1 : 0;
            int right = find(root.right,p,q) ? 1 : 0;
            int mid = (root == p) || (root == q)? 1 :0;
            //这三个位置中有两个位置找到指定节点，那么这个节点就是最近祖节点
            if(left + right + mid == 2){
                lca = root;
            }
            return (left + right + mid) > 0;//有一个节点就大于0
        }
    }
}
